package com.scqzy.shengchunqiang.sword2offer.day16;

import java.util.Arrays;

/**
 * @Description: 剑指 Offer 45. 把数组排成最小的数
 * @Author 盛春强
 * @Date 2021/8/23 15:07
 */
public class MinNumber {
    public String minNumber(int[] nums) {
        String[] strs = Arrays.stream(nums).mapToObj(String::valueOf).toArray(String[]::new);
        quickSort(strs, 0, strs.length - 1);
        return String.join("", strs);
    }

    private void quickSort(String[] strs, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(strs, left, right);
        quickSort(strs, left, pivot - 1);
        quickSort(strs, pivot + 1, right);
    }

    /**
     * 双路快排
     *
     * @Author 盛春强
     * @Date 2021/8/23 15:46
     * @Param [strs, left, right]
     * @Return int
     */
    private int partition(String[] strs, int left, int right) {
        // 比较基准值
        String pivotStr = strs[left];
        while (left < right) {
            while (left < right && (pivotStr + strs[right]).compareTo(strs[right] + pivotStr) <= 0) {
                right--;
            }
            strs[left] = strs[right];
            while (left < right && (pivotStr + strs[left]).compareTo(strs[left] + pivotStr) >= 0) {
                left++;
            }
            strs[right] = strs[left];
        }
        strs[left] = pivotStr;
        return left;
    }
}
